package cn.yza.算法.并查集;

/** 给你一个数组equations，装着若干字符串表示的算式。
 * 每个算式equations[i]长度都是 4，而且只有这两种情况：a==b或者a!=b，
 * 其中a,b可以是任意小写字母。你写一个算法，如果equations中所有算式都不会互相冲突，返回 true，否则返回 false。
  比如说，输入["a==b","b!=c","c==a"]，算法返回 false，因为这三个算式不可能同时正确。
  再比如，输入["c==c","b==d","x!=z"]，算法返回 true，因为这三个算式并不会造成逻辑冲突。

 核心思想是，将equations中的算式根据==和!=分成两部分，先处理==算式，
 使得他们通过相等关系各自勾结成门派；然后处理!=算式，检查不等关系是否破坏了相等关系的连通性。
 * @author Honglixi
 * @create 2021-11-04 21:38
 */
public class Question {
    boolean equationsPossible(String[] equations) {
        // 26 个英文字母
        UF uf = new UF(26);
        // 先让相等的字母形成连通分量
        for (String eq : equations) {
            if (eq.charAt(1) == '=') {
                char x = eq.charAt(0);
                char y = eq.charAt(3);
                uf.union(x - 'a', y - 'a');
            }
        }
        // 检查不等关系是否打破相等关系的连通性
        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                char x = eq.charAt(0);
                char y = eq.charAt(3);
                // 如果相等关系成立，就是逻辑冲突
                if (uf.connected(x - 'a', y - 'a'))
                    return false;
            }
        }
        return true;
    }
}
